package edu.android.com;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;

import android.app.Activity;
import android.graphics.Color;
import android.os.Bundle;
import android.os.Handler;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.FrameLayout;
import android.widget.TextView;
import android.widget.Toast;

public class undMST extends framework{

	private int[] father;
	private int[] rang;
	ArrayList <edge> mstEdges;
	ArrayList <edge> mstGood;
	
	@Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        
        //Visibility ...
        EditText mStartNode = (EditText)findViewById(R.id.startNode);
        mStartNode.setVisibility(EditText.INVISIBLE);
        
        
        //Start process
        Button mPickStartNode = (Button)findViewById(R.id.pickStartNode);
        
        mPickStartNode.setOnClickListener(new View.OnClickListener() {
			@Override
			public void onClick(View v) {
				// TODO Auto-generated method stub
				startThis();
			}
		});
       
        setEdgePrefereces();
    }
	
	private void setEdgePrefereces(){
		edge.mOrientated = false;
		edge.mWithCost = true;
		edge.mWithFlow = false;
	}
	
	private void setDefault(){
		int len = mNodes.size();
		used = new boolean[len + 1];
		father = new int[len + 1];
		rang = new int[len + 1];
		
		mstEdges = new ArrayList();
		mstGood = new ArrayList();
		
		for(int i = 0;i <= len;i ++){
			father[i] = i;
			rang[i] = 1;
			used[i] = false;
		}
		
		for(int i = 0;i < len;i ++){
			mNodes.get(i).initialize();
			for(int j = 0;j < mNodes.get(i).mEdges.size();j ++)
				mNodes.get(i).mEdges.get(j).setColor(Color.WHITE);
		}
	}
	
	private int getRoot(node a){
		int nd = a.getNodeNumber();
		int root = nd;
		while(root != father[root])
			root = father[root];
		
		while(nd != father[nd]){
			int aux = father[nd];
			father[nd] = root;
			nd = aux;
		}
		return root;
	}
	private void unite(int x,int y){
		if(rang[x] >= rang[y]){
			rang[x] ++;
			father[y] = x;
		}
		else{
			rang[y] ++;
			father[x] = y;
		}
	}
	
	private void startThis(){
		setDefault();
		
		if(conexGraph() == false){
			Toast.makeText(getApplicationContext(), "The current graph is not connex", Toast.LENGTH_SHORT).show();
			return ;
		}
		
		for(int i = 0;i < mNodes.size();i ++){
			for(int j = 0 ;j < mNodes.get(i).mEdges.size();j ++){
				mstEdges.add(mNodes.get(i).mEdges.get(j));
			}
		}
		
		Collections.sort(mstEdges, new myEdgeComparable());
		
		for(int i = 0;i < mstEdges.size();i ++){
			int x = getRoot(mstEdges.get(i).firstNode);
			int y = getRoot(mstEdges.get(i).secondNode);
			
			if(x != y){
				mstGood.add(mstEdges.get(i));
				unite(x,y);
			}
		}
		showToScreen();
	}
	
	private boolean conexGraph(){
		df(mNodes.get(0));
		
		for(int i = 0;i < mNodes.size();i ++){
			if(used[mNodes.get(i).getNodeNumber()] == false)
				return false;
		}
		return true;
	}
	private void df(node nd){
		used[nd.getNodeNumber()] = true;
		for(int i = 0;i < nd.mEdges.size();i ++){
			node left = nd.mEdges.get(i).firstNode;
			node right = nd.mEdges.get(i).secondNode;
			
			if(left != nd && used[left.getNodeNumber()] == false)
				df(left);
			else
				if(right != nd && used[right.getNodeNumber()] == false)
					df(right);
		}
	}
	private void showToScreen(){
		showOrder();
	}
	private void showOrder(){
		int Cost = 0;
		for(int i = 0;i <mstGood.size();i ++){
			mstGood.get(i).setColor(Color.GREEN);
			Cost += mstGood.get(i).getCost();
		}
		String toast = "Minimum spanning tree cost : " + Cost;
		mDisplayContent.setText(toast);
	}
	
	private class myEdgeComparable implements Comparator<edge>{
		 
	    @Override
	    public int compare(edge o1, edge o2) {
	        if(o1.getCost() < o2.getCost())
	        	return -1;
	        else
	        	if(o1.getCost() == o2.getCost())
	        		return 0;
	        	else
	        		return 1;
	    }
	}

}
